/***尚硅谷Java数据结构与java算法                  ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***地杰斯特拉算法        P179                   ***/
/***C++ 实现版本    written by Daniel           ***/
#include <vector>
#include <iostream>
#include <algorithm>
#include <memory>
class VisitedVertex
{
public:
    using ptr = std::shared_ptr<VisitedVertex>;
    VisitedVertex(int length, int start) : already_visited(length, false), 
        pre_visted(length, 0), distance(length, 65535)
    {
        already_visited[start] = true;
        distance[start] = 0;
    }

    int getDis(int index)
    {
        //开始节点到各个节点的距离
        return distance[index];
    }

    void setDis(int index, int dis)
    {
        this->distance[index] = dis;
    }

    bool getIsVisted(int index)
    {
        return already_visited[index];
    }

    void setVisted(int index)
    {
        already_visited[index] = true;
    }

    void setPre(int index, int pre)
    {
        pre_visted[index] = pre;
    }

    void toString()
    {
#define XX(vector)                  \
    for (const auto &item : vector) \
    {                               \
        std::cout << item << "\t";  \
    }                               \
    std::cout << std::endl;
        std::cout << "the vector of already_visited:" << std::endl;
        XX(already_visited)
        std::cout << "the vector of pre_visited:" <<std::endl;
        XX(pre_visted)
        std::cout << "the vector of distance:" << std::endl;
        XX(distance)
#undef XX
    }
    //返回中间节点，即没有被访问过，并且distance值最小的节点的下标
    int midPoint()
    {
        int min=65535, index=0;
        int len=distance.size();
        for(int i=0;i<len;i++){
            if (!already_visited[i] && distance[i]<min){
                min=distance[i];
                index=i;
            }
        }
        return index;
    }

private:
    std::vector<bool> already_visited;
    std::vector<int> pre_visted;
    std::vector<int> distance;
};

//图类
class mGraph
{
public:
    mGraph() = delete;
    mGraph(int num, std::vector<char> vertexVec, std::vector<std::vector<int>> weightVec) : vertexNum(num), vertexVec(vertexVec), weightVec(weightVec)
    { }
    mGraph(mGraph &graph) = default;
    mGraph(mGraph &&graph) = default;
    /*功能:狄杰斯特拉算法，用于确定一个节点到其他节点的最短路径
      参数： start 起点
      返回值：
    */
    void dijkstra(int start)
    {
        //创建一个智能指针
        visited = std::make_shared<VisitedVertex>(vertexNum, start);
        int index=start;
        for(int i=0;i<vertexNum;i++){
            update(index);
            index=visited->midPoint();
            visited->setVisted(index);
        }
        visited->toString();
    }
    /*
    功能：更新index下标节点到周围节点的距离和周围节点的前驱节点
    参数：index 需要更新的节点
    返回值：空
    */
    void update(int index)
    {
        int len = 0;
        for (int i = 0; i < vertexNum; i++) 
        {
            //从开始节点到i节点的距离，等与从开始节点到index的距离+index到j的距离
            len = visited->getDis(index) + weightVec[index][i];
            //
            if (!visited->getIsVisted(i) && (len < visited->getDis(i)))
            {
                visited->setPre(i, index);
                visited->setDis(i,len);
            }
            len = 0;
        }
    }

    int getIndex(char pos)
    {
        for (int i = 0; i < vertexNum; i++)
        {
            if (pos == vertexVec[i])
            {
                return i;
            }
        }
        return -1;
    }

    void printWeight()
    {
        for (const auto &item : weightVec)
        {
            for (const auto &item1 : item)
            {
                std::cout << item1 << "\t";
            }
            std::cout << std::endl;
        }
    }
private:
    int vertexNum;
    std::vector<char> vertexVec;
    std::vector<std::vector<int>> weightVec;
    VisitedVertex::ptr visited;
};


//测试代码
int main()
{
    int vertexNum = 7;
    std::vector<char> vertexVec({'A', 'B', 'C', 'D', 'E', 'F', 'G'});
    const int N = 65535;
    int arr[vertexNum][vertexNum] =
        {{N, 5, 7, N, N, N, 2},
         {5, N, N, 9, N, N, 3},
         {7, N, N, N, 8, N, N},
         {N, 9, N, N, N, 4, N},
         {N, N, 8, N, N, 5, 4},
         {N, N, N, 4, 5, N, 6},
         {2, 3, N, N, 4, 6, N}};
    std::vector<std::vector<int>> weightVec(vertexNum, std::vector<int>(vertexNum, 0));
    for (int i = 0; i < vertexNum; i++)
    {
        for (int j = 0; j < vertexNum; j++)
        {
            weightVec[i][j] = arr[i][j];
        }
    }
    mGraph *graph = new mGraph(vertexNum, vertexVec, weightVec);
    graph->printWeight();
    graph->dijkstra(6);

    if (graph != nullptr)
    {
        delete graph;
        graph = nullptr;
    }
}